/**
 * //Given an arithmetic equation consisting of positive integers, +, -, * and / (
 * //no parentheses), compute the result.
 * //
 * // The expression string contains only non-negative integers, +, -, *, /
 * //operators and empty spaces . The integer division should truncate toward zero.
 * //
 * // Example 1:
 * //
 * //
 * //Input: "3+2*2"
 * //Output: 7
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: " 3/2 "
 * //Output: 1
 * //
 * // Example 3:
 * //
 * //
 * //Input: " 3+5 / 2 "
 * //Output: 5
 * //
 * //
 * // Note:
 * //
 * //
 * // You may assume that the given expression is always valid.
 * // Do not use the eval built-in library function.
 * //
 * //
 * // Related Topics 栈 数学 字符串 👍 85 👎 0
 */

package com.xixi.dataStructure.stack;

import java.util.Stack;

public class ID_interview_16_26_CalculatorLcci {
    public static void main(String[] args) {
        Solution solution = new ID_interview_16_26_CalculatorLcci().new Solution();
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        Stack<Integer> numStack = new Stack<>();
        Stack<Character> operStack = new Stack<>();

        public int calculate(String s) {

            char[] sChar = s.toCharArray();
            int n = sChar.length;
            int i = 0;

            boolean count = false;

            //put all nums and opers into their stacks, counting multi and div
            while (i < n) {
                if (sChar[i] == ' ') {
                    i++;
                    continue; //jump ths space
                }
                if (sChar[i] == '+' || sChar[i] == '-') { //when meet plus and sub, put into the operStack
                    operStack.push(sChar[i]);
                    count = false; //先不计算
                    i++;
                } else if (sChar[i] == '*' || sChar[i] == '/') { //counting multi and div
                    char oper = sChar[i]; //save oper
                    operStack.push(sChar[i]);
                    count = true; //乘除要计算
                    i++;


                } else { //when meet nums, put into the numStack
                    //get next num
                    StringBuffer sb = new StringBuffer();
                    while (i < n && (sChar[i] >= '0' && sChar[i] <= '9')) {
                        sb.append(sChar[i]);
                        i++;
                    }
                    //Notice!!!, now sChar[i] is not a num;
                    int nextNum = Integer.parseInt(sb.toString());

                    if (count) {//要计算
                        int result = 0;
                        char oper = operStack.pop(); //save oper
                        int top = numStack.pop(); //get a top num
                        if (oper == '*') { //counting
                            result = top * nextNum;
                        } else {
                            result = top / nextNum; // save result
                        }
                        numStack.push(result);
                    } else {
                        numStack.push(nextNum);
                    }

                }

            }


            while (!operStack.isEmpty()) {
                int right = numStack.pop();
                int left = numStack.pop();
                char oper = operStack.pop();

                int result = 0;


                if (oper == '-') {
                    if (operStack.isEmpty() || operStack.peek() == '+') { //前面是正数
                        result = left - right;
                    } else { //前面是负数，符号转换
                        result = left + right;
                    }
                } else {
                    if (operStack.isEmpty() || operStack.peek() == '+') { //前面是正数
                        result = left + right;
                    } else { //前面是负数，符号转换
                        result = left - right;
                    }
                }
                numStack.push(result);

            }

            //numStack 最后就是result
            return numStack.peek();


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}